

//
//  LinkedList_find.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/8.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

extension LinkedList where Element: Equatable {
    
    /// 在整个链表中查找与element相同的第一个元素
    public func findFirst(_ element: Element) -> LinkedListNode<Element>? {
        return find(element, _header, _size)
    }
    
    /// 在整个链表中查找与element相同的最后一个元素
    public func findLast(_ element: Element) -> LinkedListNode<Element>? {
        return find(element, _size, _trailer)
    }
    
    /// 在节点p的n个真前驱(不包括p)中查找与element相同的的最后一个节点
    /// 0 <= n <= Index(p) < _size
    public func find(_ element: Element, _ n: Int, _ p: LinkedListNode<Element>) -> LinkedListNode<Element>? {
        precondition(n >= 0, "\(n)不能小于0")
        var index = 1
        var nd = p.predecessor
        while let node = nd, node !== _header {
            if index > n { return nil }
            if node.value == element {
                return node
            }
            index += 1
            nd = node.predecessor
        }
        
        return nil
    }
    
    /// 在节点p的n个真后继(不包括p)中查找与element相同的的第一个节点
    public func find(_ element: Element, _ p: LinkedListNode<Element>, _ n: Int) -> LinkedListNode<Element>? {
        precondition(n >= 0, "\(n)不能小于0")
        var index = 1
        var nd = p.successor
        while let node = nd, node !== _trailer {
            if index > n { return nil }
            if node.value == element {
                return node
            }
            index += 1
            nd = node.successor
        }
        
        return nil
    }
}
